CS156 Spring 2012Practice Final

To study for the final I would suggest you: (1) Know how to do (by heart) all the practice problems. (2) Go over your notes at least three times. Second and third time try to see how much you can remember from the first time. (3) Go over the homework problems. (4) Try to create your own problems similar to the ones I have given and solve them. (5) Skim the relevant sections from the book. (6) If you want to study in groups, at this point you are ready to quiz each other. The practice final is below. Here are some facts about the actual final: (a) It is comprehensive (b) It is closed book, closed notes. Nothing will be permitted on your desk except your pen (pencil) and test. (c) You should bring photo ID. (d) There will be more than one version of the test. Each version will be of comparable difficulty. (e) It is 10 problems, 6 problems will be on material since the lecture before the midterm, four problems will come from the topics covered prior to the midterm. (f) Two problems will be exactly (less typos) off of the practice final, and one will be off of practice midterm.

1. Define Horn clause, definite clause. Explain with an example backward chaining with regards to a Horn Program.
2. Show step-by-step how the unification algorithm would find a unifier for the A(Bob, f(x, Tom)) and A(y, f(g(Ian), z)). Assume x,y,z are variables and Bob, Tom, and Ian are constants.
3. What is the closed world assumption? What is the frame problem?
4. Consider the problem you have two socks and two shoes all of which are on the ground. You also have two feet. Your goal is to put on your shoes. Your feet can wear socks, but not shoes directly. Your available actions are to put on socks and put on shoes. Formulate this problem reasonably in PDDL. Then give an example plan solving it.
5. What is the ignore preconditions heuristics? What is the ignore delete lists heuristic?
6. Solve the shoe and sock problem you stated earlier in PDDL step-by-step using the GraphPlan algorithm.
7. Use our techniques for modeling composite objects and measurements to model the following aspects of the Angry Birds game: (a) A catapult is 3m tall. (b) A catapult is made out of a forked piece of wood and an elastic band. (c) a catapult can be used to fling a red bird, blue bird, and yellow bird.
8. Define: (a) A random variable, (b) joint distribution, (c) Baye's rule (show how can be derived)
9. Give the decision tree learning algorithm, and explain how it works on a simple example.
10. Give an example function which could be learned by a perceptron. Give an example of one which could not be learned by a perceptron. To receive credit you must give some valid reasons for your answer.